/*
 * Copyright (c) Huawei Technologies Co., Ltd. 2022-2022. All rights reserved.
 */

import { MultiMap } from '../../../../common/util/multi-map.js';

/**
 * 用于保存Hvigor的任务依赖关系的一个DAG图，提供包括添加图中节点，节点之间关系，判断节点之间是否联通等方法
 * _out和_in都是一个MultiMap，其中key是当前节点的唯一标识，即Task的path，value的大小是当前节点的入度或出度
 * _out用来保存所有以当前节点为头节点的节点信息集合,对应节点的出度
 * _in用来保存所有以当前节点为尾节点的节点信息集合，对应节点的入度
 *
 * @since 2022/4/24
 */
export class TaskDirectedAcyclicGraph {
  private _out: MultiMap = new MultiMap();
  private _in: MultiMap = new MultiMap();

  /**
   * 添加一个图中的节点
   *
   * @param {string} nodeKey
   */
  addNode(nodeKey: string): void {
    this._out.put(nodeKey);
    this._in.put(nodeKey);
  }

  /**
   * 添加两个节点之间的边,为了保证为一个有向无环图，故添加时需要判断两点之间是否已包含边
   *
   * @param {string} originKey
   * @param {string} targetKey
   * @returns {boolean}
   */
  addEdge(originKey: string, targetKey: string): boolean {
    this._out.put(originKey, targetKey);
    this._out.put(targetKey);
    this._in.put(targetKey, originKey);
    this._in.put(originKey);
    return true;
  }

  private _hasEdge(originKey: string, targetKey: string): boolean {
    if (originKey === targetKey) {
      return true;
    }
    const originChildren: Set<string> = this._out.get(originKey);
    for (const originChild of originChildren) {
      if (this._hasEdge(originChild, targetKey)) {
        return true;
      }
    }
    return false;
  }

  /**
   * 删除图中节点,同时要删除关联的起始和结束节点
   *
   * @param {string} nodeKey
   */
  removeNode(nodeKey: string): void {
    const targets = this._out.removeAll(nodeKey);
    for (const target of targets) {
      this._in.remove(target, nodeKey);
    }
    const origins = this._in.removeAll(nodeKey);
    for (const origin of origins) {
      this._out.remove(origin, nodeKey);
    }
  }

  /**
   * 清空DAG图
   */
  clear(): void {
    this._out.clear();
    this._in.clear();
  }

  /**
   * 根据节点的key获取其子节点
   *
   * @param {string} nodeKey
   * @returns {Set<string>}
   */
  getChildren(nodeKey: string): Set<string> {
    return this._out.get(nodeKey);
  }

  /**
   * 根据节点的key获取其父节点
   *
   * @param {string} nodeKey
   * @return {Set<string>}
   */
  getParent(nodeKey: string): Set<string> {
    return this._in.get(nodeKey);
  }

  /**
   * 获取所有入度为0的起始节点
   *
   * @returns {Set<string>}
   */
  getAllStartNodes(): Set<string> {
    return this.findAllZeroEdgeNodes(this._in);
  }

  /**
   * 获取所有出度为0的叶子节点
   *
   * @returns {Set<string>}
   */
  getAllEndNodes(): Set<string> {
    return this.findAllZeroEdgeNodes(this._out);
  }

  /**
   * 检查是否有环
   */
  checkCircle(): { hasCircle: boolean; circlePath: string[] } {
    const visited = new Set<string>();
    const onStack = new Set<string>();

    const allNodes = this._out.keys();
    const returnResult: { node?: string } = {};
    for (const node of allNodes) {
      if (this.dfsCircleCheck(node, visited, onStack, returnResult)) {
        return {
          hasCircle: true,
          circlePath: [...onStack, returnResult.node!],
        };
      }
    }

    return {
      hasCircle: false,
      circlePath: [],
    };
  }

  private dfsCircleCheck(node: string, visited: Set<string>, onStack: Set<string>, returnResult: { node?: string }): boolean {
    if (onStack.has(node)) {
      // 记录成环开始的node
      returnResult.node = node;
      return true;
    }

    if (visited.has(node)) {
      return false;
    }

    visited.add(node);
    onStack.add(node);

    for (const childNode of this.getChildren(node)) {
      if (this.dfsCircleCheck(childNode, visited, onStack, returnResult)) {
        return true;
      }
    }
    onStack.delete(node);
    return false;
  }

  private findAllZeroEdgeNodes(map: MultiMap): Set<string> {
    const result = new Set<string>();
    map.keys().forEach((nodeKey: string) => {
      const nodeChildren: Set<string> = map.get(nodeKey);
      if (nodeChildren.size === 0) {
        result.add(nodeKey);
      }
    });
    return result;
  }
}

/**
 * 整个工程需要一个全局单一的DAG图用来保存和执行模块之间的任务依赖
 */
export const projectTaskDag = new TaskDirectedAcyclicGraph();
